// 定义一个名为 BSTOperations 的类，用于执行二叉搜索树（BST）的各种操作
// 定义二叉树节点类

public class BSTOperations {
    // 向二叉搜索树中插入一个值为 val 的节点
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // 如果根节点为空，创建一个新节点并返回
        if (root == null) {
            return new TreeNode(val);
        }
        // 如果插入的值小于当前节点的值，将其插入到左子树中
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            // 否则，将其插入到右子树中
            root.right = insertIntoBST(root.right, val);
        }
        // 返回更新后的根节点
        return root;
    }

    // 检查二叉树是否为有效的二叉搜索树
    public boolean isValidBST(TreeNode root) {
        // 调用辅助方法进行检查，初始范围为负无穷到正无穷
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // 辅助方法，用于递归检查二叉树是否为有效的二叉搜索树
    private boolean isValidBST(TreeNode node, long min, long max) {
        // 如果节点为空，认为是有效的
        if (node == null) {
            return true;
        }
        // 如果节点的值不在允许的范围内，不是有效的 BST
        if (node.val <= min || node.val >= max) {
            return false;
        }
        // 递归检查左子树和右子树
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }

    // 从二叉搜索树中删除值为 key 的节点
    public TreeNode deleteNode(TreeNode root, int key) {
        // 如果根节点为空，直接返回 null
        if (root == null) {
            return null;
        }
        // 如果要删除的值小于当前节点的值，在左子树中删除
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            // 如果要删除的值大于当前节点的值，在右子树中删除
            root.right = deleteNode(root.right, key);
        } else {
            // 找到要删除的节点
            if (root.left == null) {
                // 如果左子树为空，返回右子树
                return root.right;
            } else if (root.right == null) {
                // 如果右子树为空，返回左子树
                return root.left;
            }
            // 左右子树都不为空，找到右子树中的最小节点
            TreeNode minNode = findMin(root.right);
            // 将最小节点的值赋给当前节点
            root.val = minNode.val;
            // 在右子树中删除最小节点
            root.right = deleteNode(root.right, root.val);
        }
        // 返回更新后的根节点
        return root;
    }

    // 找到以 node 为根的子树中的最小节点
    private TreeNode findMin(TreeNode node) {
        // 不断向左遍历，直到找到最左边的节点
        while (node.left != null) {
            node = node.left;
        }
        // 返回最小节点
        return node;
    }

    public static void main(String[] args) {
        // 创建 BSTOperations 类的实例
        BSTOperations bst = new BSTOperations();
        // 初始化根节点为 null
        TreeNode root = null;
        // 插入节点 5
        root = bst.insertIntoBST(root, 5);
        // 插入节点 3
        root = bst.insertIntoBST(root, 3);
        // 插入节点 7
        root = bst.insertIntoBST(root, 7);
        // 插入节点 2
        root = bst.insertIntoBST(root, 2);
        // 插入节点 4
        root = bst.insertIntoBST(root, 4);

        // 检查插入节点后是否为有效的 BST 并输出结果
        System.out.println("Is valid BST: " + bst.isValidBST(root));

        // 删除值为 3 的节点
        root = bst.deleteNode(root, 3);
        // 检查删除节点后是否为有效的 BST 并输出结果
        System.out.println("Is valid BST after deletion: " + bst.isValidBST(root));
    }
}

